// step 1# 定义宏：取最大值
#define max(a, b) ((a) > (b) ? (a) : (b))

// step 2# 主函数：划分字母区间
int* partitionLabels(char* s, int* returnSize) {
    // step 2.1# 记录每个字符最后一次出现的位置
    int last[26] = {0}; // 只考虑小写字母
    int len = strlen(s);
    for (int i = 0; i < len; ++i) {
        last[s[i] - 'a'] = i;
    }

    // step 2.2# 初始化左右指针和返回数组
    int left = 0, right = 0;
    int *partition = malloc(sizeof(int) * len); // 最多len个区间
    *returnSize = 0;

    // step 2.3# 遍历字符串，动态扩展当前区间
    for (int i = 0; i < len; i++) {
        // step 2.3.1# 更新当前区间最远能到的位置
        right = max(right, last[s[i] - 'a']);

        // step 2.3.2# 如果遍历到区间末尾
        if (i == right) {
            // step 2.3.3# 记录当前区间长度
            partition[(*returnSize)++] = right - left + 1;
            // step 2.3.4# 更新下一个区间的起点
            left = i + 1;
        }
    }

    // step 2.4# 返回区间划分结果
    return partition;
}
